home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 280_01 / sort.c < prev    next >
Text File  |  1989-01-11  |  8KB  |  385 lines
  1. /* [SORT.C of JUGPDS Vol.46]*/
  2. /*
  3. *****************************************************************
  4. *                                *
  5. *    Written by  Hakuo Katayose (JUG-CP/M No.179)        *
  6. *            49-114 Kawauchi-Sanjuunin-machi        *
  7. *            Sendai, Miyagi 980                          *
  8. *            Phone: 0222-61-3219                *
  9. *                                *
  10. *       Modifird by Toshiya Oota   (JUG-CPM No.10)              *
  11. *                   Sakae ko-po 205                 *
  12. *            5-19-6 Hosoda                *
  13. *            Katusikaku Tokyo 124            *
  14. *                                *
  15. *        for MS-DOS Lattice C V3.1J & 80186/V20/V30    *
  16. *                                *
  17. *    Compiler Option: -ccu -k0(1) -ms -n -v -w        *
  18. *                                *
  19. *    Edited & tested by Y. Monma (JUG-CP/M Disk Editor)    *
  20. *            &  T. Ota   (JUG-CP/M Sub Disk Editor)    *
  21. *                                *
  22. *****************************************************************
  23. */
  24.  
  25. /* sort - sort and merge */
  26.  
  27. #include "stdio.h"
  28. #include "dos.h"
  29. #include "tools.h"
  30. #include "toolfunc.h"
  31.  
  32. #define LINES    4000
  33. #define MAXLEN    128
  34. #define MAXBUF    16
  35. #define MERGEORDER    7
  36.  
  37. char    allocbuf[1024][MAXBUF], *alloc_bp, *alloc_ep;
  38. char    opt_d;        /* dictionary order */
  39. char    opt_f;        /* fold order        */
  40. char    opt_n;        /* numeric order   */
  41. char    opt_l;        /* line_no listing  */
  42. char    opt_r;        /* reverse order    */
  43.  
  44. void FileSort(),Sort(),MakeFile(),Fcopy(),Gopen(),Gremove(),Merge();
  45. void reheap(),sort(),quick(),Ptext(),putdec(),fputlin(),putch(),fputdec();
  46.  
  47. void main(argc, argv)
  48. int argc;
  49. char *argv[];
  50. {
  51. char    *ap;
  52. int    i;
  53.  
  54.     if (argc <3)
  55.     error("SRT999 Usage: sort -{dfnlr} file1 file2 ... >outfile");
  56.     else
  57.     opt_d = opt_f = opt_n = opt_l = opt_r = OFF;
  58.     i = 0;
  59.     while ( (*++argv)[0] == '-' ) {
  60.     for (ap = argv[0]+1; *ap != NULL; ap++)
  61.         switch (tolower(*ap)) {
  62.         case 'd':
  63.         { opt_d = ON;break;};
  64.         case 'f':
  65.         { opt_f = ON;break;};
  66.         case 'n':
  67.         { opt_n = ON;break;};
  68.         case 'l' :
  69.         { opt_l = ON;break;};
  70.         case 'r':
  71.         { opt_r = ON;break;};
  72.         }
  73.     argc--;
  74.     }
  75.     if (argc < 1)
  76.     error("SRT999 Usage: sort -{dfnlr} file1 file2 ... >outfile");
  77.  
  78.     FileSort(argc-1 , argv);
  79. }
  80.  
  81. void FileSort(argc,argv)
  82. int  argc;
  83. char **argv;
  84. {
  85. static    char    *lineptr[LINES];
  86. char    fname[15], outfname[15], opt_ll;
  87. int    nlines, t, high, low, lim;
  88. FILE    *infp[MERGEORDER], *outfp;
  89.  
  90.     low = -1;
  91.     high = 0;
  92.     opt_ll = opt_l;
  93.     opt_l  = OFF;
  94.     do {
  95.     do {
  96.         if( (infp[++low] = fopen(*(argv++),READ) )== NO) {
  97.         fprintf(STDERR, "SRT911 file not open: %s\n", *(argv - 1) );
  98.         exit(1);
  99.         }
  100.         t = Gtext(lineptr, &nlines, LINES, infp[low]);
  101.         Sort(lineptr, &nlines);
  102.         MakeFile(low, &outfp, outfname);
  103.         Ptext(lineptr, nlines, outfp);
  104.         putc(CPMEOF,outfp);
  105.         if(fclose(outfp) == ERROR) {
  106.         fprintf(STDERR, "SRT912 file close error: %s\n", outfname);
  107.         exit(1);
  108.         }
  109.     } while (t != EOF);
  110.     } while (--argc > 0);
  111.     high = low + 1;
  112.     opt_l = opt_ll;
  113.     for (low = 0; low < high; low += MERGEORDER) {
  114.     lim = min(low + MERGEORDER - 1, high);
  115.     Gopen(infp, low, lim);
  116.     MakeFile(++high, &outfp, outfname);
  117.     Merge(infp, lim-low, outfp);
  118.     putc(CPMEOF,outfp);
  119.     fclose(outfp);
  120.     Gremove(infp, low, lim);
  121.     }
  122.     sprintf(fname, "stemp.$%d", high);
  123.     if ((infp[high] = fopen(fname,READ)) == NO) {
  124.     fprintf(STDERR, "SRT901 file not open: %s\n", fname);
  125.     exit(1);
  126.     }
  127.     Fcopy(infp[high], STDOUT);
  128.     fclose(infp[high]);
  129.     unlink(fname);
  130. }
  131.  
  132. void MakeFile(fno, fp, fname)
  133. FILE    **fp;
  134. int    fno;
  135. char    *fname;
  136. {
  137.     sprintf(fname, "stemp.$%d", fno);
  138.     if ((*fp = fopen(fname,WRITE)) == NO) {
  139.     fprintf(STDERR, "SRT902 file not creat: %s\n", fname);
  140.     exit(1);
  141.     }
  142. }
  143.  
  144. void Fcopy(inbuf, outbuf)
  145. FILE *inbuf, *outbuf;
  146. {
  147. int  lno;
  148.     lno = 1;
  149.     while (fgetlin(inbuf, allocbuf, MAXLEN) > 0) {
  150.     if( opt_l == ON )
  151.         fputdec(outbuf, lno++, 6);
  152.         fputlin(outbuf, allocbuf);
  153.         if (outbuf != STDOUT)
  154.         putch(NEWLINE, outbuf);
  155.     }
  156. }
  157.  
  158. void Gopen(fp, low, lim)
  159. FILE    *fp[];
  160. int    low,lim;
  161. {
  162. int    i;
  163. char    fname[15];
  164.     for (i = 0; i < lim - low ; i++) {
  165.     sprintf(fname, "stemp.$%d", low + i);
  166.     if ((fp[i] = fopen(fname,READ)) == NO) {
  167.         fprintf(STDERR, "SRT903 file not open: %s\n", fname);
  168.         exit(1);
  169.     }
  170.     }
  171. }
  172.  
  173. void Gremove(fp, low, lim)
  174. FILE    *fp[];
  175. {
  176. char    fname[15];
  177. int    i;
  178.     for (i = 0; i < lim - low; i++) {
  179.     putc(CPMEOF, fp[i]);
  180.     if(fclose(fp[i]) == ERROR) {
  181.         fprintf(STDERR, "SRT912 file can't close : %s\n", fp[i]);
  182.         exit(1);
  183.     };
  184.     sprintf(fname, "stemp.$%d", low + i);
  185.     unlink(fname);
  186.     }
  187. }
  188.  
  189. /* merge - merge infile(1)...infile(nfiles) onto outfile */
  190. void Merge(infile, nfiles, outfile)
  191. FILE    *infile[], *outfile;
  192. int    nfiles;
  193. {
  194. char    *lineptr[MERGEORDER], *p;
  195. int    i, nl, inf, len;
  196. int    strcmp(), numcmp(), swap();
  197.  
  198.     p = alloc_bp = &(allocbuf[0][0]);
  199.     for (nl = 0, i = 0; i < nfiles; i++)
  200.         if ((len = fgetlin(infile[i], alloc_bp, MAXLEN)) > 0) {
  201.             *(alloc_bp + len - 1) = '\0';
  202.             lineptr[nl++] = alloc_bp;
  203.             alloc_bp += MAXLINE;
  204.         }
  205.     Sort(lineptr, &nl);
  206.     nl--;
  207.     while (nl >= 0) {
  208.         fputlin(outfile, lineptr[0]);
  209.         putch(NEWLINE, outfile);
  210.         inf = (lineptr[0] - p) / MAXLINE;
  211.         if ((len =fgetlin(infile[inf], lineptr[0], MAXLEN)) <= 0)
  212.             lineptr[0] = lineptr[nl--];
  213.         else
  214.             *(lineptr[0] + len - 1) = '\0';
  215.         if (opt_n == ON)
  216.             reheap(lineptr, nl, numcmp, swap);
  217.         else if (opt_d == ON && opt_f == ON)
  218.             reheap(lineptr, nl, strdfcmp, swap);
  219.         else if (opt_d == ON)
  220.             reheap(lineptr, nl, strdcmp, swap);
  221.         else if (opt_f == ON)
  222.             reheap(lineptr, nl, strfcmp, swap);
  223.         else
  224.             reheap(lineptr, nl, strcmp, swap);
  225.         }
  226. }
  227.  
  228. /* reheap - propagat inbuf(lineptr(1)) to proper place in heap */
  229. void reheap(lineptr, nl, comp, exch)
  230. char    *lineptr[];
  231. int    (*comp)(), (*exch)();
  232. int    nl;
  233. {
  234. int    i, f;
  235.  
  236.     for (i = 1; i <= nl; i++) {
  237.         f = (*comp)(lineptr[i-1], lineptr[i]);
  238.         if (opt_r == ON && f >= 0)
  239.             break;
  240.         else if (opt_r==OFF && f <= 0)
  241.             break;
  242.         (*exch)(&lineptr[i-1], &lineptr[i]);
  243.     }
  244. }
  245.  
  246. void Sort(lineptr, nlines)
  247. char *lineptr[];
  248. int  *nlines;
  249. {
  250. int    numcmp(), swap();
  251.  
  252.     if (opt_n == ON)
  253.         quick(lineptr, 0, (*nlines)-1, numcmp, swap);
  254.     else if (opt_d == ON && opt_f == ON)
  255.         quick(lineptr, 0, (*nlines)-1, strdfcmp, swap);
  256.     else if (opt_d == ON)
  257.         quick(lineptr, 0, (*nlines)-1, strdcmp, swap);
  258.     else if (opt_f == ON)
  259.         quick(lineptr, 0, (*nlines)-1, strfcmp, swap);
  260.     else
  261.         quick(lineptr, 0, (*nlines)-1, strcmp, swap);
  262. }
  263.  
  264. numcmp(s1, s2)
  265. char *s1, *s2;
  266.  
  267. {
  268. int    atoi(), v1, v2;
  269.     v1 = atoi(s1);
  270.     v2 = atoi(s2);
  271.     if (v1 < v2)
  272.         return(-1);
  273.     else if (v1 > v2)
  274.         return(1);
  275.     else
  276.         return(0);
  277. }
  278.  
  279. Gtext(lineptr, nlines, maxlines, fp)
  280. char    *lineptr[];
  281. int    *nlines, maxlines;
  282. FILE    *fp;
  283.  
  284. {
  285. int    len;
  286.     *nlines = 0;
  287.     alloc_bp = &(allocbuf[0][0]);
  288.     alloc_ep = &allocbuf[1023][(MAXBUF-1)];
  289.     do {
  290.         if ((len = fgetlin(fp, alloc_bp, MAXLEN)) <= 0)
  291.             return EOF;
  292.         lineptr[(*nlines)++] = alloc_bp;
  293.         alloc_bp += len;
  294.         *(alloc_bp - 1) = NULL;
  295.         } while (alloc_bp + MAXLEN <= alloc_ep && *nlines < maxlines);
  296.     return(len);
  297. }
  298.  
  299. void  Ptext(lineptr, nlines, fp)
  300. char    *lineptr[];
  301. int    nlines;
  302. FILE    *fp;
  303.  
  304. {
  305. int    lno;
  306.     lno = 1;
  307.     if (opt_r == ON) lineptr += nlines;
  308.     while (nlines--) {
  309.         if (opt_l == ON)
  310.             fputdec(fp, lno++, 6);
  311.         fputlin(fp, (opt_r == ON ? *--lineptr : *lineptr++));
  312.         putch(NEWLINE, fp);
  313.         }
  314. }
  315.  
  316. /* fputdec - put decimal integer in field width >= w for FILE *fp */
  317. void fputdec(fp, n, w)
  318. FILE *fp;
  319. int  n,w;
  320. {
  321. char    s[64];
  322. int    len;
  323.     len = strlen(itoa(s,n));
  324.     if ((len = w - len) > 0)
  325.         while (len--)
  326.             putch(BLANK, fp);
  327.     fputlin(fp, s);
  328.     putch(':', fp);
  329. }
  330.  
  331. void fputlin(fp, s)
  332. char *s;
  333. FILE *fp;
  334. {
  335.     while (*s)
  336.         putch(*s++, fp);
  337. }
  338.  
  339. void putch(c,fp)
  340. FILE *fp;
  341. {
  342.     if (fp == STDOUT)
  343.         putchar(c);
  344.     else {
  345.         if (c == NEWLINE)
  346.             putc(CRETURN, fp);
  347.         putc(c, fp);
  348.     }
  349. }
  350.  
  351. fgetlin(fp, s, lim)
  352. char    *s;
  353. int    lim;
  354. FILE    *fp;
  355.  
  356. {
  357.     char    *p;
  358.     int    c;
  359.  
  360.     p = s;
  361.     while (--lim > 0 && (c = getch(fp)) != EOF && c != NEWLINE)
  362.         *s++ = c;
  363.     if(c == NEWLINE)
  364.         *s++ = c;
  365.     *s = '\0';
  366.     return(s-p);
  367. }
  368.  
  369. getch(fp)
  370. FILE *fp;
  371.  
  372. {
  373.     int    c;
  374.  
  375.     if (fp == STDIN)
  376.         return (int) getchar();
  377.     else {
  378.         if ((c = getc(fp)) == CRETURN)
  379.